package structure

import (
	"math"
)

/**
 * 单源最短路径，迪杰斯特拉算法
 * @since 2022/8/5 10:35
 * @author 李磊
 */
func djstl(citys [][]int, i, j int) (int, []int) {
	distance := make([]int, len(citys))
	lastNode := make(map[int]int, len(citys))
	for k := range distance {
		distance[k] = citys[i][k]
		if citys[i][k] != math.MaxInt {
			lastNode[k] = i
		}
	}

	for m := range citys {
		if citys[i][m] == math.MaxInt {
			continue
		}
		//深度优先搜索?不大对的样子
		dg(citys, m, distance, lastNode)
	}

	nodes := make([]int, 0, len(citys))
	nodes = append(nodes, j)
	last := j
	for {
		x := lastNode[last]
		nodes = append(nodes, x)
		if x == i {
			break
		}
		last = x
	}
	reverse(nodes)
	return distance[j], nodes
}

func reverse(slice []int) {
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
}

func dg(citys [][]int, m int, distance []int, lastNode map[int]int) {
	for n := range citys[m] {
		if citys[m][n] != math.MaxInt {
			if distance[m]+citys[m][n] < distance[n] {
				distance[n] = distance[m] + citys[m][n]
				lastNode[n] = m
				dg(citys, n, distance, lastNode)
			}
		}
	}
}
